C 算法设计

考点

算法设计是下午软件设计中最难的题型，主要难在 C 代码填空上。

1. 代码填空：第一小题，最后解决。
2. 算法、时间复杂度：第二题，先做，考察何种算法很好分辨，涉及到分组就是分治法，局部最优就是贪心法，整体规划最优就是动态规划法，迷宫类的问题就是回溯法，记住关键字很好区分；时间复杂度就是看 C 代码中的 for 循环层数和每一层的循环次数，涉及到二分必然有 $O(log_n)$。
3. 特殊值计算：第三小题，一般应该先做，不需要根据 C 代码，直接根据题目给出的算法原理，一步步推导即可得出答案

算法类型判断

算法基本上只考四种，分治算法、动态规划算法、贪心法、回溯法，在题目中找关键字。

• 出现最优、最大、最小： 从动态规划法和贪心法中寻找，贪心法是局部最优；动态规划法是全局最优，要求每一步子结构都是最优的，动态规划法会使用递归的思想去求，一般会给出最优子结构的递归式。
• 有分而治之的思想，就是分治法
• 回溯法： 回溯

算法一

动态规划法：最优子结构、递归、公式

算法二

算法三

出现最优，选动态规划法和贪心法，出现递归公式，则为动态规划法。

算法四

出现最优，选动态规划法和贪心法，出现递归公式，则为动态规划法。

算法五

分而治之的思想，分治法 ，不是二分查找法

算法六

贪心法：求最优，但没有最优子结构、递归等。